package net.tp.struct.bst;

import net.tp.struct.tree.TreePrinter;
import net.tp.util.Wrappers;
import net.tp.struct.tree.BinNode;
import static net.tp.util.Utils.*;

import java.util.Comparator;

/**
 *
 * <p>Splay Tree.</p>
 *
 * <p>Splay tree is a self-adjusting binary search tree that has an average $O(log(n))$ time (amortized) / operations.</p>
 *
 * <p>The splay tree has some interesting properties.
 * Assuming the tree stores keys {1, 2, 3, ..., n} (so that the value of the element is also the rank). Suppose we
 * search for $x_1, x_2, ... x_m$, where $x_i$ is a value searched at time $i$, so $x_{i-1}$ is the previously accessed
 * element of $x_i$.</p>
 *
 * <ul>
 *     <li>Static optimality (or entropy bound property): in a sequence of accessing keys, if key $k$ has probability $p_k$,
 *     then the cost of access per operation is $∑↙{k=1}↖n p_k log(1/p_k)$.</li>
 *     <li>Working set property: if an element is accessed recently, accessing that element again should be fast.
 *     Suppose we search for $x_i = v$, if there are k distinct keys accessed since last access
 *     to the key $v$, then accessing $x_i$ takes $O(log(k))$ time. This property implies the static optimality property.</li>
 *     <li>Dynamic finger property: accessing an element that is close to the previously accessed element should be fast.
 *     The closeness is measure in the rank difference. Dynamic finger property implies sequential access property.
 *     Suppose the rank difference between the $x_i$ and $x_{i-1}$ is k (i.e. $|x_i-x_{i-1}| = k$),
 *     then accessing $x_i$ should take $O(log(k))$ time.</li>
 *     <li>Sequential access property: in-order traversal should take constant time.
 *     Accessing in-order $1, 2, 3 ..., n$ should take $O(1)$ time since $|x_i-x_{i-1}|=1$.</li>
 *     <li>Dynamic optimality (not proven): it's a conjecture that splay tree is as asymptotically fast on any
 *     sequence of operations as any other type of search trees with rotation, i.e. is splay tree is $O(1)$-competitive?
 *     Note: every BST is $O(log(n))$-competitive, the best known so far is tango tree which is $O(log log(n))$-competitive.</li>
 * </ul>
 *
 * <p>Any sequence of operations in splay tree takes amortized $O(log(n))$ time per operation. Sometimes, it's faster. For example,
 * it's proven that sequence of search operations from the smallest to largest key takes total time $O(n)$ time, or amortized $O(1)$
 * per operation.</p>
 *
 * <p>One disadvantage of splay tree is that the height of the tree can be linear. This happens when inserting elements
 * in sequence order.</p>
 *
 * <p>This is the example or inserting sequence of 0-9 into a splay tree, then do a sequence of operations from smallest key 0 to
 * the largest key 9:</p>
 *
 * <p>Inserting values 0-1-2-3-4-5-6-7-8-9 into an empty splay tree:</p>
 *
 * <pre style="overflow:auto">
 * 0     1      2         3      ...                      9
 *      ┌┴┐    ┌┴─┐     ┌─┴─┐                           ┌─┴─┐
 *      0      1        2                               8
 *            ┌┴┐      ┌┴─┐                           ┌─┴─┐
 *            0        1                              7
 *                    ┌┴┐                           ┌─┴─┐
 *                    0                             6
 *                                                ┌─┴─┐
 *                                                5
 *                                              ┌─┴─┐
 *                                              4
 *                                            ┌─┴─┐
 *                                            3
 *                                          ┌─┴─┐
 *                                          2
 *                                         ┌┴─┐
 *                                         1
 *                                        ┌┴┐
 *                                        0
 * </pre>
 *
 * <p>Searching for 0 would take $O(n)$ time, however the inserting 0-9 takes $O(1)$ time per operation. So on average, it
 * takes $O(1)$ time per operation.</p>
 *
 * <p>Search for 0-1-2-3-4-5-6-7-8-9, again, the first few search takes longer, the later, the search is much faster, making it
 * average $O(1)$ time per search operation.</p>
 *
 * <pre style="overflow:auto">
 *
 *       0               1             2                 3                4                  5                   6                     7                     8                     9
 *  ┌────┴────┐       ┌──┴──┐        ┌─┴──┐           ┌──┴───┐          ┌─┴──┐             ┌─┴──┐              ┌─┴──┐                ┌─┴──┐                ┌─┴─┐                 ┌─┴─┐
 *            9       0     7        1    3           2      7          3    5             4    7              5    7                6    9                7   9                 8
 *          ┌─┴─┐        ┌──┴──┐    ┌┴┐ ┌─┴──┐       ┌┴─┐  ┌─┴─┐      ┌─┴─┐ ┌┴─┐         ┌─┴─┐ ┌┴─┐          ┌─┴─┐ ┌┴─┐            ┌─┴─┐ ┌┴┐             ┌─┴─┐                 ┌─┴─┐
 *          7            3     9    0        7       1     5   9      2        7         3     6  9          4        9            5     8               6                     7
 *        ┌─┴─┐         ┌┴─┐  ┌┴┐          ┌─┴─┐    ┌┴┐   ┌┴┐ ┌┴┐    ┌┴─┐     ┌┴─┐     ┌─┴─┐     ┌┴┐       ┌─┴─┐     ┌┴┐         ┌─┴─┐                 ┌─┴─┐                 ┌─┴─┐
 *        5   8         2  5  8            5   9    0     4 6 8      1        6  9     2         8         3         8           4                     5                     6
 *      ┌─┴─┐             ┌┴┐             ┌┴┐ ┌┴┐                   ┌┴┐         ┌┴┐   ┌┴─┐               ┌─┴─┐                 ┌─┴─┐                 ┌─┴─┐                 ┌─┴─┐
 *      3   6             4 6             4 6 8                     0           8     1                  2                     3                     4                     5
 *     ┌┴─┐                                                                                             ┌┴─┐                 ┌─┴─┐                 ┌─┴─┐                 ┌─┴─┐
 *     1  4                                                                                             1                    2                     3                     4
 *    ┌┴┐                                                                                              ┌┴┐                  ┌┴─┐                 ┌─┴─┐                 ┌─┴─┐
 *      2                                                                                                                   1                    2                     3
 *                                                                                                                         ┌┴┐                  ┌┴─┐                 ┌─┴─┐
 *                                                                                                                                              1                    2
 *                                                                                                                                             ┌┴┐                  ┌┴─┐
 *                                                                                                                                             0                    1
 *                                                                                                                                                                 ┌┴┐
 *                                                                                                                                                                 0
 * </pre>
 *
 * <h3>Splay operation:</h3>
 * <p>Splay tree depends heavily on splay operation which moves a recently accessed node to the root position when
 * searching or modifying elements.</p>
 * <p>There are three cases to move a node into the root:</p>
 *
 * <p>Zig case: if the node is a child of root, then rotate the node to make it root:</p>
 *
 * <pre>
 *             R           rotate x ⇒                       X
 *          ┌──┴──┐                                      ┌──┴──┐
 *          X     △                                      △     R
 *        ┌─┴─┐   3                                      1   ┌─┴─┐
 *        △   △                                              △   △
 *        1   2                                              2   3
 * </pre>
 *
 * <p>Zig-zig case: when node x and its parent are both left child or right child:</p>
 *
 * <pre>
 *              ┊                                             ┊
 *              G          rotate p, rotate x ⇒               X
 *          ┌───┴───┐                                     ┌───┴───┐
 *          P       △                                     △       P
 *       ┌──┴──┐    4                                     1    ┌──┴──┐
 *       X     △                                               △     G
 *     ┌─┴─┐   3                                               2   ┌─┴─┐
 *     △   △                                                       △   △
 *     1   2                                                       3   4
 * </pre>
 *
 * <p>Zig-zag case: when node x is left child and parent is right child or node x is right child and parent is left child:</p>
 *
 * <pre>
 *              ┊                                             ┊
 *              G          rotate x, rotate x ⇒               X
 *          ┌───┴───┐                                     ┌───┴───┐
 *          P       △                                     P       G
 *       ┌──┴──┐    4                                   ┌─┴─┐   ┌─┴─┐
 *       △     X                                        △   △   △   △
 *       1   ┌─┴─┐                                      1   2   3   4
 *           △   △
 *           2   3
 * </pre>
 *
 *
 * <h3>Search operation:</h3>
 * <p>Search for x from root, if search is successful, splay node x to the root. Example: search for C</p>
 * <pre>
 *          F          zig-zag ⇒              C*
 *     ┌────┴────┐                       ┌────┴────┐
 *     B         G                       B         F
 *  ┌──┴──┐                           ┌──┴──┐   ┌──┴──┐
 *  A     C*                          A         D     G
 *      ┌─┴─┐
 *          D
 * </pre>
 *
 * <p>If search is not successful, splay the last non-null node in the search path to the root. Example: search for E</p>
 * <pre>
 *          F          zig-zig ⇒              F        rotate D ⇒        D*
 *     ┌────┴────┐                       ┌────┴────┐                  ┌──┴──┐
 *     B         G                       D*        G                  C     F
 *  ┌──┴──┐                           ┌──┴──┐                       ┌─┴─┐ ┌─┴─┐
 *  A     C                           C                             B         G
 *      ┌─┴─┐                       ┌─┴─┐                         ┌─┴─┐
 *          D*                      B                             A
 *                                ┌─┴─┐
 *                                A
 * </pre>
 *
 * <h3>Insert operation:</h3>
 * <p>Search for node x, if the search is successful, splay the node to the root.</p>
 * <p>If the search is not successful, insert new node as the child of the last non-null node in the search path,
 * then splay the new node to the root.</p>
 *
 * <h3>Delete operation:</h3>
 * <p>Search for node x to delete, if the search is not successful, splay the last non-null node in the search path to the root.</p>
 * <p>If the search is successful, remember the parent node p of this node. Delete the key
 * as normal BST, then splay the parent p to the root.</p>
 * <pre style="overflow:auto">
 *                       I               delete D ⇒                       I              splay F ⇒                  F*
 *               ┌───────┴───────┐                                ┌───────┴───────┐                         ┌───────┴───────┐
 *               G               J                                G               J                         C               G
 *          ┌────┴────┐     ┌────┴────┐                      ┌────┴────┐     ┌────┴────┐               ┌────┴────┐     ┌────┴────┐
 *          F*        H               K                      F*        H               K               A         E               I
 *      ┌───┴───┐                                        ┌───┴───┐                                 ┌───┴───┐                 ┌───┴───┐
 *      D*                                               C                                                 B                 H       J
 *   ┌──┴──┐                                          ┌──┴──┐                                                                     ┌──┴──┐
 *   A     E                                          A     E                                                                           K
 * ┌─┴─┐                                            ┌─┴─┐
 *     C                                                B
 *    ┌┴┐
 *    B
 * </pre>
 *
 *
 *
 * @author Trung Phan
 *
 */
public class SplayTree<E> {

    private final Comparator<? super E> comparator;
    private BinNode<E> root;

    public SplayTree() {
        this(naturalComparator());
    }

    public SplayTree(Comparator<? super E> comparator) {
        this.comparator = comparator;
    }

    public boolean empty() {
        return root == null;
    }

    public int size() {
        return root == null ? 0 : root.size;
    }

    public boolean contains(E element) {
        if (root == null) {
            return false;
        }

        BinNode<E> node = find(element);

        splay(node);

        return comparator.compare(element, node.element) == 0;
    }

    public void add(E element) {
        if (root == null) {
            root = new BinNode<>(element);
            return;
        }

        BinNode<E> node = find(element);

        int c = comparator.compare(element, node.element);
        if (c == 0) {
            // found the element, so just splay the node
            splay(node);
        }
        else if (c < 0) {
            assert node.left == null;
            node.bindLeft(new BinNode<>(element));
            node.updateSizeCascade();
            splay(node.left);
        }
        else {
            assert node.right == null;
            node.bindRight(new BinNode<>(element));
            node.updateSizeCascade();
            splay(node.right);
        }

    }

    public boolean remove(E element) {
        if (root == null) return false;

        BinNode<E> node = find(element);

        if (comparator.compare(element, node.element) == 0) {
            BinNode<E> nodeToSplay = node.parent;

            if (node.left != null && node.right != null) {
                // found 2 children, need to find successor
                BinNode<E> successor;
                for (successor = node.right; successor.left != null; successor = successor.left);
                node.element = successor.element; // exchange the element
                node = successor;
            }

            BinNode<E> parent = node.parent;
            node.parent = null;
            BinNode<E> child = node.left == null ? node.right : node.left;
            if (child != null) child.parent = parent;
            if (parent == null) {
                root = child;
            }
            else if (parent.left == node) {
                parent.left = child;
                parent.updateSizeCascade();
            }
            else if (parent.right == node) {
                parent.right = child;
                parent.updateSizeCascade();
            }
            else throw new IllegalStateException();

            if (nodeToSplay != null) {
                splay(nodeToSplay);
            }

            return true;
        }
        else {
            splay(node);
            return false;
        }
    }

    private void splay(BinNode<E> node) {
        while (node != root) {
            if (node.parent == root) {
                node.rotate();
                root = node;
            }
            // zig-zig case
            else if ((node.parent.left == node && node.parent.parent.left == node.parent) ||
                    (node.parent.right == node && node.parent.parent.right == node.parent)) {
                node.parent.rotate();
                node.rotate();
                if (node.parent == null) root = node;
            }
            // zig-zag case
            else {
                node.rotate();
                node.rotate();
                if (node.parent == null) root = node;
            }
        }
    }

    private BinNode<E> find(E element) {
        BinNode<E> n = root;
        while (true) {
            int c = comparator.compare(element, n.element);
            if (c == 0) {
                return n;
            }
            else if (c < 0) {
                if (n.left != null) n = n.left;
                else return n;
            }
            else {
                if (n.right != null) n = n.right;
                else return n;
            }
        }
    }

    @Override
    public String toString() {
        return TreePrinter.toString(root, BinNode::getChildren);
    }
}
